\section{GSM and A5/2 overview}

In the GSM protocol the authentication process consists of the network
authenticating the SIM at the beginning of a radio conversation between the 
mobile phone and the network. This authentication procedure is initiated by the 
network when a mobile phone has identified itself by sending its TMSI. It is a 
challenge-response scheme\footnote{This scheme is described in \cite{stinson}
section 9.2, page 356.} based on a pre-shared key $K_i$ between the mobile phone
and the network, and works as follows:

The network sends a 128-bit random number $RAND$ to the mobile phone, which
transfers it to its SIM. The SIM then calculates a response:
\be{SRES}
SRES = A3(K_i, RAND)
\ee
where $A3$ is a one-way function\footnote{A hash function where the three
problems described in \cite{stinson} section 4.2, page 121 are difficult to solve.}.

The mobile phone sends $SRES$ calculated by the SIM to the network where it
is compared to the $SRES$ value pre-calculated by the network. In parallel to
this authentication procedure an encryption key $K_c$ for the conversation is
created:
\be{Kc}
K_c = A8(K_i, RAND)
\ee
where $A8$ is also a one-way function.

Now, the remainder of the phone call can be encrypted using $K_c$, and the
mobile phone and the network remain authenticated due to the fact that are both
using the same encryption key. However, one thing to remember is that encryption
is not mandatory and is controlled by the network. So it would be possible for
an attacker to impersonate the network using a fake base station with no
encryption.

When setting up a network, the operators can independently decide the exact
design of the one-way functions $A3$ and $A8$. Many choose an example from the
GSM memorandum of understanding called 'COMP128'. However, COMP128 was reverse
engineered \cite{bgw} and cryptanalysis made it possible to find the pre-shared
key $K_i$. Given $K_i$, $A3$ and $A8$ it is possible to perform cloning of a
network. An attacker then requires the $SRES$ values for $2^{17}$ values of
$RAND$, and the data required can be obtained using a fake base station within a
few hours.

$A5/1$ was the name of the original encryption algorithm for GSM. But when the
system grew beyond Europe a new algorithm was needed, as $A5/1$ was export
restricted. The encryption algorithm chosen to replace $A5/1$ was called $A5/2$
and was of a weaker design than its predecessor. The internal design of both
algorithms was kept secret and was disclosed only on a need-to-know basis to GSM
manufacturers. In 1999 the internal design of $A5/1$ and $A5/2$ was reverse
engineered \cite{bgw2} from an actual GSM phone. A new version called $A5/3$ was
created in 2002 and its design was published. The $A5/3$ cipher will be
introduced later in this paper, and is based on the block cipher KASUMI, which
is used in third generation networks (3GPP).

In 2003 it was demonstrated \cite{bbk} that the GSM protocol was vulnerable
against a man-in-the-middle attack that allowed avoiding the $A5/3$ cipher. This
attack will be described in more detail later. The attack requires only that the
network supports $A5/1$ or $A5/3$, and that the mobile phone supports $A5/2$.
The attacker could then impersonate the mobile phone to the network and vice
versa by using a fake base station. He could then use $A5/1$ for communication
with the network and $A5/2$ for communication with the mobile phone. Both
algorithms would encrypt using the same key, and the attacker could uncover it
by using the passive attack on $A5/2$.

In 2010 an attack on $A5/3$ was discovered \cite{dks} that allows to recover the
$A5/3$ key in two hours on a modern personal computer, but this attack lies
outside of the scope of this paper, and may not be applicable to the way $A5/3$
is used in 3G systems.

\subsection{A5/2}
The $A5/2$ is a stream-cipher that uses four Linear Feedback Shift Registers
(LFSR), a clocking function and a majority function to produce an output bit to the
key-stream every cycle. 

We will denote the four registers as $R1$, $R2$, $R3$ and $R4$ where $R1$, $R2$,
$R3$ are the registers that are used to produce the output bits and $R4$ is used
to determine which of the three registers are to be clocked each round. $R4$ is
always clocked at the end of each round. The $i$'th bit of one register $Rj$
will be denoted as $Rj[i]$.

$R4$ uses a clocking function to determine which of the three other registers
are to be clock for at given round. The clocking function takes three bits as
input :
$R4[3]$, $R4[7]$ and $R4[10]$ and calculates the majority of these bits. The
clocking is determined after these rules:
\begin{itemize}
	\item If $R4[10]$ agrees with the result, then $R1$ is clocked
	\item If $R4[3]$ agrees with the result, then $R2$ is clocked
	\item If $R4[7]$ agrees with the result, then $R3$ is clocked. 
\end{itemize}

For each of the registers, if we look at the bit string as a vector, one
clocking can be described as a matrix multiplication where we define a matrix
$Li$ for the $i$'th register. $L1$ will be a $[18 \times 18]$ matrix where the
first row will be:
\be{firstRow}
	[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1]
\ee
and the last column containing zero's in all entries except for the first row.
The remaining $[17 \times 17]$ is the identity matrix that makes sure to shift all
the other bits one place to the right. We can express the clocking of the other
registers with a matrix as well.

The majority function, which is quadratic in its input is defined by:
\be{maj}
	maj(a,b,c) = a \cdot b \oplus b \cdot c \oplus c \cdot a 
\ee 
The output from each of the majority functions will be denoted as $H_i$ for the
$i$'th register. For example the output from the majority function for $R1$ the output
is calculated like:
\be{majR1}
	\begin{split}
		H_1& = maj(x_{12},(x_{14} \oplus 1),x_{15})\\
	   	   & = x_{12}(x_{14} \oplus 1) \oplus (x_{14} \oplus 1)x_{15} \oplus
	   	   x_{15}x_{12}\\
	   	   & = x_{12}x_{14} \oplus x_{12} \oplus x_{14}x_{15} \oplus x_{15} \oplus
	   	   x_{15}x_{12}
	\end{split}	
\ee
and similar for $R2$ and $R3$ with their respective inputs to the $maj$
function.

An output bit in the key-stream will be calculated by :
\be{outputbit}
	outputbit = H_1 \oplus R1[18] \oplus H_2 \oplus R2[21] \oplus H_3 \oplus
	R3[22]
\ee

\subsection{Generating the keystream}
When generating a key-stream for GSM, and the $A5/2$ algorithm is used, the key
is a product of a known initialization vector, called $COUNT$ where $|COUNT| = 22$,
that is derived from the frame counter, and the session-key $K_c$, where
$|K_c| = 64$, that both the mobile unit and the network knows, we will denote
the value of $COUNT$ as $f$.

The generation of the key-stream can be divided into three steps. 
\begin{itemize}
  \item Initialize the registers with $K_c$ and $COUNT$
  \item Run 99 cycles of $A5/2$
  \item Run 228 cycles of $A5/2$ and use the output as the key
\end{itemize}
We will look at each step and explain how they are done.

The first step is the initialization of the registers. This part can also be
split up into four steps:\\
\begin{algorithmic}\label{keysetup}
 \STATE Set $R1 = R2 = R3 = R4 = 0$
 \FOR{$i = 0$ to $63$}
	\STATE Clock all four registers
	\STATE $R1[0] \leftarrow R1[0] \oplus K_c[i]; R2[0] \leftarrow R2[0] \oplus
	 K_c[i]; R3[0] \leftarrow R3[0] \oplus K_c[i]; R4[0] \leftarrow R4[0] \oplus K_c[i];$
 \ENDFOR
 \FOR{$i = 0$ to $21$}
 	\STATE Clock all four registers
	\STATE $R1[0] \leftarrow R1[0] \oplus f[i]; R2[0] \leftarrow R2[0] \oplus f[i];
	R3[0] \leftarrow R3[0] \oplus f[i]; R4[0] \leftarrow R4[0] \oplus f[i];$
\ENDFOR
 \STATE Set $R1[15] = R2[16] = R3[18] = R4[10] = 1$
\end{algorithmic}
After initialization the algorithm is run 99 cycles and then discard the
output.

Finally we are ready to produce our key-stream, which is the next 228 bits that
is outputted by the algorithm. This key is split into to parts of 114 bits. The
first part is used by the network to encrypt messages, and the second part is
used by the mobile unit to encrypt messages. Since both parties have each
others keys, they are mutually authenticated.

\subsection{A5/1}
	The main difference between $A5/1$ and $A5/2$ is that $A5/2$ uses three bits
	from the $R4$ register to decide which registers to clock. That is not the case with
	$A5/1$ as it uses one bit from each register as input to the clocking function,
	to decide which registers to clock.\\
	The key-setup is the same for the two algorithms, except that $A5/1$ does not
	initialize $R4$ since it does not use it and instead of discarding 99 cycles
	output before beginning to generate key bits, $A5/1$ discards 100 cycles
	output.
	
We have had some problems determining why the two algorithms runs for 99 and 100
cycles before the key-stream is generated, but one could suspect that the
designers of the algorithms would do this to get away from the initial state and
make the bits of every register depend on more than just the initial input to
make each variable dependant on $\oplus$ of all the other bits.
